
<!DOCTYPE html>
<html>

	<head>
	<title>CAIJL's Blog</title>
	<meta charset="utf-8"/>
	<link rel="stylesheet" href="/font-awesome-4.7.0/css/font-awesome.min.css">

	<link rel="stylesheet" href="/bootstrap-3.3.7/css/bootstrap.min.css">
	<script src="/jquery-2.1.1/jquery.min.js"></script>
	<script src="/bootstrap-3.3.7/js/bootstrap.min.js"></script>

	<link rel="stylesheet" href="/css/bootstrap-slider.min.css">
	<script src="/js/bootstrap-slider.min.js"></script>
	
	<link rel="stylesheet" href="/css/main.css">
	<script src="/js/main.js"></script>
	
	<link rel="stylesheet" href="/css/cursor.css">
	<script src="/js/cursor.js"></script>
	
	
	<link rel="stylesheet" href="/css/code.css">
	<!--link rel="stylesheet" href="/css/markdown.css"-->
	
	<link rel="stylesheet" href="/css/head.css">

	<script src="/js/window.js"></script>
	<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
	</head>
<body>

	<link rel="stylesheet" href="/katex/katex.min.css" crossorigin="anonymous">
	<script src="/katex/katex.min.js" crossorigin="anonymous"></script>
	<script src="/katex/contrib/mathtex-script-type.min.js" defer></script>
	<script defer src="/katex/contrib/auto-render.min.js"crossorigin="anonymous"
	    onload="renderMathInElement(document.body);"></script>
	<script>document.addEventListener("DOMContentLoaded", function() {renderMathInElement(document.body,{"delimiters":[{left: "$", right: "$", display: false}]});});</script>
	<nav class="navbar navbar-default header card" role="navigation" style="width: 100%;">
	<div class="container-fluid"> 
	<div class="navbar-header">
		<button type="button" class="navbar-toggle" data-toggle="collapse"
				data-target="#example-navbar-collapse">
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
		</button>
		<a class="navbar-brand" href="/"><span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="bold">C</mi><mi mathvariant="bold">A</mi><mi mathvariant="bold">I</mi><mi mathvariant="bold">J</mi><msup><mi mathvariant="bold">L</mi><mo mathvariant="bold" lspace="0em" rspace="0em">′</mo></msup><mi mathvariant="bold">s</mi><mi mathvariant="bold">B</mi><mi mathvariant="bold">L</mi><mi mathvariant="bold">O</mi><mi mathvariant="bold">G</mi></mrow><annotation encoding="application/x-tex">\mathbf{CAIJL'sBLOG}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height: 0.751892em; vertical-align: 0em;"></span><span class="mord"><span class="mord mathbf">C</span><span class="mord mathbf">A</span><span class="mord mathbf">I</span><span class="mord mathbf">J</span><span class="mord"><span class="mord mathbf">L</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height: 0.751892em;"><span class="" style="top: -3.063em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathbf mtight">′</span></span></span></span></span></span></span></span></span><span class="mord mathbf">s</span><span class="mord mathbf">B</span><span class="mord mathbf">L</span><span class="mord mathbf">O</span><span class="mord mathbf">G</span></span></span></span></span></span></a>
	</div>
	<div class="collapse navbar-collapse" id="example-navbar-collapse">
		<ul class="nav navbar-nav" style="background-color:#fcfcfc">
			<li><a href="/"><i class="menu-item-icon fa fa-fw fa-home"></i>首页</a></li>
			<li><a href="/archives/"><i class="menu-item-icon fa fa-fw fa-archive"></i>文章</a></li>
			<li><a href="/tags/"><i class="menu-item-icon fa fa-fw fa-tags"></i>标签</a></li>
			<li><a href="/settings/"><i class="menu-item-icon fa fa-fw fa-cogs"></i>设置</a></li>
			<!--li><a href="/about/"><i class="menu-item-icon fa fa-fw fa-user"></i>关于</a></li-->
			<li><a href="/games/"><i class="menu-item-icon fa fa-fw fa-gamepad"></i>其它</a></li>
			

		</ul>
	</div>
	</div>
	</nav>
<div class="container">
	<div style="height: 60px;"></div>
	<div class="row" >
		<div class="col-md-8">
			<div class="panel panel-default card" style="padding: 10px;position: relative;">
                <img src='/img/bg/50.png' style="width:100%"/>
				<span style="position: absolute;left:15px;bottom:15px;width:90%;"><font class="view-text" style="color:#fcfcfc;font-size:25px">数数：从入门到放弃</font><br><a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/笔记/" class="tag"><span  style="background-color: rgb(82, 196, 26);">笔记</span></a></span>
			</div>
			<div class="panel panel-default card" style="padding: 10px;" id="main">
                <h1 id="_1">前前言</h1>
<h2 id="_2">参考资料</h2>
<p><a href="https://www.luogu.com.cn/blog/command-block/sheng-cheng-han-shuo-za-tan">多项式计数杂谈</a></p>
<p><a href="https://www.luogu.com.cn/blog/zyxxs/x-yi-x-jiang-tan-sheng-cheng-han-shuo-ru-men">【x义x讲坛】生成函数入门</a></p>
<h2 id="_3">膜拜巨佬</h2>
<p>%%%太强啦 <a href="https://www.luogu.com.cn/user/151935">Rainbow_sjy❤OI</a> <a href="https://www.luogu.com.cn/user/220857">素质玩家孙1超</a></p>
<h1 id="_4">前言</h1>
<p>首先是最基础的一些数数，相信大家都会吧。</p>
<p>阶乘：从 <script type="math/tex">1</script> 乘到 <script type="math/tex">n</script> 的结果，记做 <script type="math/tex">n!</script>
</p>
<p>排列数：从 <script type="math/tex">n</script> 个不同元素中任取 <script type="math/tex">m(m\le n)</script> 个元素排成一列（考虑元素先后出现次序）称此为一个排列，此种排列的总数即为排列数，记做 <script type="math/tex">A_n^m</script> ，有 <script type="math/tex">A_n^m=\frac{n!}{m!}</script>
</p>
<p>组合数：从 <script type="math/tex">n</script> 个不同元素中取出 <script type="math/tex">m(m\le n)</script>个元素的所有组合的个数，叫做从 <script type="math/tex">n</script> 个不同元素中取出 <script type="math/tex">m</script> 个元素的组合数，记做 <script type="math/tex">C_n^m</script> 或 <script type="math/tex">\tbinom{n}{m}</script> ，有：<script type="math/tex">C_n^m=\frac{n!}{m!(n-m)!}</script>
</p>
<p>这些定义我们后面还可以拓展，但我们现在先不去管它。</p>
<p>还有一些应该知道的数学基础：</p>
<h1 id="_5">简单数学基础</h1>
<h2 id="_6">简单微积分入门</h2>
<h3 id="_7">导数的基本运算：</h3>
<p>
<script type="math/tex; mode=display">\begin{aligned}
&(F(x)±G(x))^\prime=F^\prime(x)±G^\prime(x)\\
&(a\times F(x))^\prime=c F^\prime(x)\\
&(F(x)\times G(x))^\prime=
F^\prime(x)G(x)+F(x)G^\prime(x)\\
&\left(\frac{F(x)}{G(x)}\right)'=\dfrac{F'(x)G(x)-F(x)G'(x)}{G^2(x)}
\end{aligned}</script>
</p>
<h3 id="_8">单项式求导/求原:</h3>
<p>
<script type="math/tex; mode=display">(x^i)^\prime=ix^{i-1}\Leftrightarrow \int x^idx=\frac{x^{i+1}}{i+1}</script>
</p>
<h3 id="_9">链式求导法则/复合函数求导：</h3>
<p>
<script type="math/tex; mode=display">\frac{d}{du}\frac{du}{dx}=\frac{d}{dx}\\</script>
<script type="math/tex; mode=display">v(u(x))\frac{d}{dx}=v^\prime(u(x))\times u^\prime(x)</script>
</p>
<h3 id="_10">泰勒展开/麦克劳林级数</h3>
<p>设 <script type="math/tex">F^{(n)}(x)</script> 为 <script type="math/tex">F(x)</script> 的 <script type="math/tex">n</script> 阶导数，我们考虑一个多项式，使其在 <script type="math/tex">x=a</script> 处零阶导数一阶导数、二阶导数……无穷阶导数与 <script type="math/tex">F(x)</script> 的对应导数相同，那么这两个函数就完全相同：
<script type="math/tex; mode=display">F(x)=\sum\limits_{i=0}\dfrac{F^{(i)}(a)}{i!}(x-a)^i</script>
在 <script type="math/tex">x=0</script> 处泰勒展开
<script type="math/tex; mode=display">F(x)=\sum\limits_{i=0}\dfrac{F^{(i)}(0)}{i!}x^i</script>
</p>
<p>利用这个，我们可以用多项式表示 <script type="math/tex">\exp x</script> 、 <script type="math/tex">\sin x</script> 、 <script type="math/tex">\cos x</script>，大家可以自己试试看。</p>
<h3 id="_11">多项式牛顿迭代</h3>
<p>若 <script type="math/tex">G(F(x))=0</script>
</p>
<p>加入我们已知 <script type="math/tex">G(F_0(x))=0 \pmod {x^n}</script>
</p>
<p>那么有 <script type="math/tex">F(x)=F_0(x)-\frac{G(F_0(x))}{G^\prime(F_0(x))} \pmod{x^{2n}}</script>
</p>
<p>这个可以用泰勒展开证明：
<script type="math/tex; mode=display">G(F(x))=\frac{G(F_0(x))}{0!}+\frac{G^\prime(F_0(x))}{1!}(F(x)-F_0(x))+\frac{G^{\prime\prime}F_0(x)}{2!}(F(x)-F_0(x))^2+\ldots</script>
关注 <script type="math/tex">(F(x)-F_0(x))^2</script> ,发现 <script type="math/tex">F(x)</script> 与 <script type="math/tex">F_0(x)</script> 的前 <script type="math/tex">n</script> 项是相等的，最低次至少为 <script type="math/tex">x^n</script> ,平方后就是 <script type="math/tex">x^{2n}</script>，再取模是把它给“截断了”</p>
<p>化简就能得到一开始的结论了。</p>
<h4 id="1">例题1：一个方程</h4>
<blockquote>
<p>Using the chain rule is like peeling an onion: you have to deal with each layer at a time, and if it is too big you will start crying。</p>
</blockquote>
<p>这里化一个比较麻烦的方程，等下可能会用到：
<script type="math/tex">G(x)=x\exp \frac{2F(x)-F(x)^2}{2-2F(x)}-F(x)</script>
</p>
<p>我们让 <script type="math/tex">G(x)</script> 对 <script type="math/tex">F(x)</script> 求导，可以得到：
<script type="math/tex; mode=display">G^\prime(F(x))=x\times \exp \frac{2F(x)-F(x)^2}{2-2F(x)}\times (\frac{2F(x)-F(x)^2}{2-2F(x)})^\prime-1=</script>
为了让推导更加简洁，我们令<script type="math/tex">H(x)=x\times \exp \frac{2F_0(x)-F_0(x)^2}{2-2F_0(x)}</script>，然后就可以列出迭代式了：
<script type="math/tex; mode=display">\begin{aligned}
F(x)&=F_0(x)-\frac{G(F_0(x))}{G^\prime(F_0(x))}\\
&=F_0(x)-\frac{H(x)-F_0(x)}{H(x)\times (\frac{2F_0(x)-F_0(x)^2}{2-2F_0(x)})^\prime-1}\\
&=F_0(x)-\frac{2H(x)-2F_0(x)}{(1+\frac{1}{(F(x)-1)^2})H(x)-2}
\end{aligned}</script>
中间跳去的步骤留给读者自己思考 <del>我绝对不会说是编辑器太卡了</del></p>
<h2 id="_12">阶乘幂引入</h2>
<h3 id="_13">下降幂 :</h3>
<p>
<script type="math/tex; mode=display">x^{\underline{n}}=\overbrace{x(x-1)(x-2)\ldots(x-n+1)}^{\text{共}n\text{个因子}}</script>
注意当 <script type="math/tex">n<0</script> 时下降幂仍有意义：
<script type="math/tex; mode=display">x^{\underline{-n}}=\dfrac{1}{(x+1)(x+2)\ldots(x+n)}</script>
</p>
<h3 id="_14">上升幂：</h3>
<p>
<script type="math/tex; mode=display">x^{\overline{n}}=\overbrace{x(x+1)(x+2)\ldots(x+n-1)}^{\text{共 n 个因子}}</script>
类似的有 <script type="math/tex">n<0</script>
<script type="math/tex; mode=display">x^{\overline{-n}}=\dfrac{1}{(x-1)(x-2)\ldots(x-n)}</script>
</p>
<p>两者统称为<strong>阶乘幂</strong>。</p>
<p>有一些简单的性质：
<script type="math/tex; mode=display">x^{\overline{a+b}}=x^{\overline{a}}(x+a)^{\overline{b}}</script>
<script type="math/tex; mode=display">x^{\underline{a+b}}=x^{\underline{a}}(x-a)^{\overline{b}}</script>
以及上升幂与下降幂的转化：
<script type="math/tex; mode=display">x^{\overline{n}}=(-1)^n(-x)^{\underline{n}}</script>
<script type="math/tex; mode=display">x^{\underline{n}}=(-1)^n(-x)^{\overline{n}}</script>
来考虑前者：
<script type="math/tex; mode=display">
\begin{aligned}
x^{\overline{n}}&=x(x+1)(x+2)\ldots(x+n-1)\\ 
&=(-1)^n(-x)(-x-1)(-x-2)\ldots(-x-n+1)\\
&=(-1)^n(-x)^{\underline n}
\end{aligned}
</script>
一些有趣的性质由于笔者还不会就咕咕咕了。</p>
<h2 id="_15">广义二项式系数&amp;广义二项式定理</h2>
<p>二项式定理：
<script type="math/tex; mode=display">(x+y)^n=\sum_{i=0}^n\tbinom{n}{i}x^iy^{n-i}</script>
</p>
<p>
<script type="math/tex">\tbinom{n}{m}</script> 表示 <script type="math/tex">n</script> 个里选 <script type="math/tex">m</script> 个的方案数
<script type="math/tex; mode=display">\tbinom{n}{m}=\frac{n!}{m!(n-m)!}</script>
此时要求 <script type="math/tex">n,m</script> 都为整数且<script type="math/tex">m\le n</script>。可以换一种写法：
<script type="math/tex; mode=display">\tbinom{n}{m}=\frac{n^{\underline{m}}}{m!}</script>
显然正确。</p>
<p>现在我们的组合数对于实数也有意义了。因为对于实数为底并不影响下降幂的计算。</p>
<p>现在我们的二项式定理的 <script type="math/tex">n</script> 也就不再局限于正整数了。用 <script type="math/tex">\alpha</script> 重写柿子，区分一下上式 <del>（其实因为博客里都是α</del></p>
<p>
<script type="math/tex; mode=display">(x+y)^\alpha=\sum_{i=0}^\infty \tbinom{\alpha}{i}x^iy^{n-i}</script>
</p>
<p>普通的二项式只要取到 <script type="math/tex">n</script> 是因为后面的下降幂会变成 <script type="math/tex">0</script>
</p>
<p>只需证明 <script type="math/tex">(1+z)^\alpha=\sum_{i=0}^\infty \tbinom{\alpha}{i}z^i</script> ，然后令 <script type="math/tex">z=\frac{x}{y}</script> ,两边同乘 <script type="math/tex">y^\alpha</script> 即可。</p>
<p>不难发现
<script type="math/tex; mode=display">
\begin{aligned}
((1+z)^\alpha)^{(i)}
&=(\alpha(1+z)^{\alpha-1})^{(i-1)}\\
&=(\alpha(\alpha-1)(1+z)^{\alpha-2})^{(i-2)}\\
&=\ldots\\
&=\alpha^{\underline{i}}(1+z)^{\alpha-i}
\end{aligned}
</script>
于是带入麦克劳林级数得到：
<script type="math/tex; mode=display">(1+z)^\alpha=\sum_{i=0}^\infty\frac{\alpha^{\underline{i}}}{i!}z^i=\sum_{i=0}^\infty\tbinom{\alpha}{i}z^i</script>
不过要注意当 <script type="math/tex">z\not\in(-1,1)</script> 时上式发散，不过求系数倒是不影响。</p>
<h3 id="_16">上指标反转</h3>
<p>
<script type="math/tex; mode=display">\tbinom{r}{k}=(-1)^k\tbinom{k-r-1}{k}</script>
理解：两数分母字样，分子<script type="math/tex">r^{\underline{k}}=(-1)^k(-r)^{\overline{k}}=(-1)^k(k-r-1)^{\underline{k}}</script>
</p>
<p>接下来就可以进行一些<strong>魔法</strong>了</p>
<h3 id="tbinom2nn">
<script type="math/tex">\tbinom{2n}{n}</script>的封闭形式</h3>
<p>
<script type="math/tex; mode=display">\sum_{n=0}^\infty\tbinom{2n}{n}x^n</script>
考虑下降幂的定义，我们发现
<script type="math/tex; mode=display">
\begin{aligned}
x^{\underline{k}}(x-\frac12)^{\underline{k}}&=\frac{2x\times (2x-2)\times\ldots\times (2k-2k+2) \times (2x-1)\times(2x-3)\times\ldots\times(2x-2k+1)}{2^{2k}}\\
&=\frac{2x\times (2x-1)\times (2x-2) \times(2x-3)\times\times\ldots\times(2k-2k+2)\times(2x-2k+1)}{2^{2k}}\\
&=\frac{(2x)^{\underline{2k}}}{2^{2k}}
\end{aligned}</script>
令 <script type="math/tex">x=k=n</script> ，得到：<script type="math/tex">n^{\underline{n}}(n-\frac12)^{\underline{n}}=\frac{(2n)^{\underline{2n}}}{4^n}</script>
</p>
<p>考虑用拆开右边的 <script type="math/tex">(2n)^{\underline{2n}}=(2n)^{\underline{n}}n^{\underline{n}}</script>
</p>
<p>于是两边就可以消去一些东西了：<script type="math/tex">(n-\frac12)^{\underline{n}}=\frac{(2n)^{\underline{n}}}{4^n}</script>
</p>
<p>两边同除 <script type="math/tex">n!</script> 得到我们喜闻乐见的组合数：<script type="math/tex">4^n\tbinom{n-\frac12}{n}=\tbinom{2n}{n}</script>
</p>
<p>用一下我们刚刚的指标反转：<script type="math/tex">4^n(-1)^n\tbinom{-\frac12}{n}=\tbinom{2n}{n}</script>
</p>
<p>于是我们就可以来化简了 <script type="math/tex">
\sum_{n=0}^\infty\tbinom{2n}{n}x^n=\sum_{n=0}^\infty\tbinom{-\frac12}{n}(-4x)^n</script>
</p>
<p>于是我们可以得到一个非常优美的柿子：
<script type="math/tex; mode=display">\sum_{n=0}^\infty\tbinom{2n}{n}x^n=\frac{1}{\sqrt{1-4x}}</script>
</p>
<p>这个柿子我们后面还会用到。</p>
<h1 id="_17">生成函数</h1>
<p>对于一个数列 <script type="math/tex">a_0,a_1,a_2,\ldots</script> ，我们可以搞一个函数来描述这个序列，然后就可以用一些数学<strong>魔法</strong>来解决一些问题。形式化地，我们定义：</p>
<p>
<script type="math/tex; mode=display">F(x)=a_0f_0(x)+a_1f_a(x)+a_2f_2(x)+\ldots</script>
</p>
<p>这里的 <script type="math/tex">f_k(x)</script> 我们随便搞出来的标志函数。我们称 <script type="math/tex">F(x)</script> 为数列 <script type="math/tex">\{a_0,a_1,a_2,\ldots\}</script> 的<strong>母函数</strong>，也称为生成函数。</p>
<p>那么现在我们只需要研究函数就可以解决一些实际问题了。</p>
<h2 id="mathbfogf">普通生成函数 <script type="math/tex">\mathbf{OGF}</script>
</h2>
<p>如果我们定义 <script type="math/tex">f_k(x)=x^k</script> ，就能得到最普通的一类生成函数，即<strong>普通生成函数</strong>（<script type="math/tex">\mathbf{OGF}</script>，<script type="math/tex">\rm ordinary\quad generating\quad function</script>），来看一下这个奇怪的函数：</p>
<p>
<script type="math/tex; mode=display">F(x)=a_0+a_1x^1+a_2x^2+\ldots</script>
</p>
<h3 id="1_1">例题1：简单背包问题</h3>
<p>现在我们先来看一个简单例题：有 <script type="math/tex">\rm 1g</script> 的砝码三个， <script type="math/tex">\rm 3g</script> 的砝码一个， <script type="math/tex">\rm 5g</script> 的砝码一个，求凑出 <script type="math/tex">\rm 10g</script> 的方案数。</p>
<p>当然可以背包，但从生成函数来看，这个答案就是 <script type="math/tex">(1+x+x^2+x^3)(1+x^3)(1+x^5)</script>的<script type="math/tex">x^{10}</script>的系数，记为 <script type="math/tex">[x^{10}]\ (1+x+x^2+x^3)(1+x^3)(1+x^5)</script>。</p>
<p>上边的问题为什么可以这么求解？其实本质还是因为多项式乘法：</p>
<p>
<script type="math/tex; mode=display">[x^n](F(x)\times G(x))=\sum_{i=0}^nF_iG_{n-i}</script>
</p>
<p>就类似于 <script type="math/tex">\rm dp</script> 的思想， 根据乘法原理，<script type="math/tex">n</script> 的方案数来自于就是两个子问题的方案，且与多项式乘法惊人地吻合。想通了这一点，上面的例题也就迎刃而解了。</p>
<p>现在来看几个常用的普通生成函数：</p>
<p>
<script type="math/tex; mode=display">
\boxed{
\begin{aligned}
&\{1,1,1,1,\ldots\}\stackrel{\mathbf{OGF}}{\longrightarrow}\frac{1}{1-x}\\
&\{\overbrace{1,1,1,\ldots,1}^n\}\stackrel{\mathbf{OGF}}{\longrightarrow}\frac{1-x^{n+1}}{1-x}\\
&\{0,1,0,1,\ldots\}\stackrel{\mathbf{OGF}}{\longrightarrow}\frac{x}{1-x^2}\\
&\{1,c,c^2,c^3,\ldots\}\stackrel{\mathbf{OGF}}{\longrightarrow}\frac{1}{1-cx}\\
\end{aligned}
}
</script>
</p>
<p>这里只证明第二个柿子（逃：
<script type="math/tex; mode=display">
\begin{aligned}
1+&x+x^2+\ldots+x^{n-1}+x^n=S&(1)\\
&x+x^2+\ldots+x^{n-1}+x^n+x^{n+1}=xS&(2)\\
\end{aligned}
</script>
</p>
<p>
<script type="math/tex">(2)-(1),x^{n+1}-1=(x-1)S</script>，即<script type="math/tex">S=\frac{1-x^{n+1}}{1-x}</script>。</p>
<p>发现若是 <script type="math/tex">x\in(-1,1)</script> :
<script type="math/tex; mode=display">\lim_{n\to +\infty}\frac{1-x^{n+1}}{1-x}=\frac{1}{1-x}</script>
这也就证明了第一个柿子。</p>
<p>但现在的左右两边只有当<script type="math/tex">x\in(-1,1)</script>才成立。但我们做生成函数只考虑系数，不用管范围。</p>
<p>其他柿子都是同理。</p>
<h3 id="2">例题2：斐波那契数列</h3>
<p>记斐波那契数列的第 <script type="math/tex">i</script> 项为 <script type="math/tex">fib_i</script> ，那么有： <script type="math/tex">fib_0=0,fib_1=1,fib_n=fib_{n-1}+fib_{n-2}</script>
</p>
<p>令 <script type="math/tex">F(x)=\sum_{i=0}^{+\infty}fib_ix^i</script> ，即 <script type="math/tex">\mathbf{OGF}\{fib_0,fib_1,fib_2,\ldots\}</script>：</p>
<p>
<script type="math/tex; mode=display">
\begin{alignedat}{2}
F(x)&=fib_0+&fib_1\times x+&fib_2\times x^2+fib_3\times x^3+fib_4\times x^4+\ldots(1)\\
xF(x)&=&fib_0\times x+&fib_1\times x^2+fib_2\times x^3+fib_3\times x^4+\ldots(2)\\
x^2F(x)&=&&fib_0\times x^2+fib_1\times x^3+fib_2\times x^4+\ldots(3)\\
\end{alignedat}
</script>
</p>
<p>
<script type="math/tex">(2)</script> 式加 <script type="math/tex">(3)</script> 式，由于 <script type="math/tex">fib_i+fib_{i+1}=fib_{i+2}</script> ，可以得到：</p>
<p>
<script type="math/tex; mode=display">(x+x^2)F(x)=fib_2\times x^2+fib_3\times x^3+fib_4\times x^4\ldots</script>
</p>
<p>与 <script type="math/tex">(1)</script> 式对比一下，有：</p>
<p>
<script type="math/tex; mode=display">F(x)=(x+x^2)F(x)+x</script>
</p>
<p>可以得到一个非常优美的柿子：</p>
<p>
<script type="math/tex; mode=display">F(x)=\frac{x}{1-x-x^2}</script>
</p>
<p>称之为<strong>封闭形式</strong>。</p>
<p>利用这个我们甚至还可以反推通项公式：</p>
<p>设 <script type="math/tex">x_{1,2}</script> 为方程 <script type="math/tex">x^2+x-1=0</script> 的两根，那么就可以把 <script type="math/tex">\frac{x}{1-x-x^2}</script> 化为我们喜闻乐见的 <script type="math/tex">\frac{1}{1-cx}</script> 的形式：</p>
<p>
<script type="math/tex; mode=display">
\begin{aligned}
F(x)&=-\frac{x}{x^2+x-1}=-\frac{x}{(x-x_1)(x-x_2)}\\
&=\frac{x}{x_1-x_2}(\frac{1}{x-x_1}-\frac{1}{x-x_2})\\
&=\frac{x}{x_1-x_2}(-\frac{1}{x_1}\frac{1}{1-x/x_1}+\frac{1}{x_2}\frac{1}{1-x/x_2})\\
&=\frac{1}{x_1-x_2}(
-\frac{1}{x_1}\sum_{i=0}^\infty \frac{x^{i+1}}{x_1^i}
+\frac{1}{x_2}\sum_{i=0}^\infty \frac{x^{i+1}}{x_2^i}
)\\
&=\frac{1}{x_1-x_2}(
-\sum_{i=1}^\infty \frac{x^i}{x_1^i}
+\sum_{i=1}^\infty \frac{x^i}{x_2^i}
)
\end{aligned}
</script>
提取系数得到 <script type="math/tex">[x^n]F(x)=\frac{1}{x_1-x_2}(\frac{1}{x_2^n}-\frac{1}{x_1^n})</script> ，把 <script type="math/tex">x_{1,2}</script> 带入，得到了大名鼎鼎的斐波那契通项公式：</p>
<p>
<script type="math/tex; mode=display">fib_n=\dfrac{\sqrt{5}}{5}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]</script>
</p>
<p>思考题： <script type="math/tex">G(x)=\frac{1}{x^2+1}</script> ，求 <script type="math/tex">[x^n]G(x) \bmod 998244353</script>
</p>
<h3 id="3">例题3：卡塔兰数</h3>
<p>
<script type="math/tex">C_0=1,C_n=n\text{对括号合法序列数}</script>
<script type="math/tex">(n>1)</script>
</p>
<p>口胡出递推方程：</p>
<p>
<script type="math/tex; mode=display">C_{n+1}=\sum_{i=0}^nC_iC_{n-i}</script>
</p>
<p>也就是枚举第一对括号里放了多少东西。</p>
<p>来考虑 <script type="math/tex">C_i</script> 的生成函数 <script type="math/tex">C(x)</script> ,发现：</p>
<p>
<script type="math/tex; mode=display">xC^2(x)+1=C(x)</script>
</p>
<p>就是<script type="math/tex">C(x)</script>自卷、右移一位(对应<script type="math/tex">n+1</script>)、强制令<script type="math/tex">C_0=1</script>
</p>
<p>我们用自身表示了自己，根据求根公式不难得到：
<script type="math/tex; mode=display">C(x)=\dfrac{1±\sqrt{1-4x}}{2x}</script>
</p>
<p>现在出现了两个根，应该取哪一个呢？根据定义，对于一个<script type="math/tex">\mathbf{OGF}</script> ,当<script type="math/tex">x\to0</script>时应该是收敛的，那么我们来验证一下：</p>
<ul>
<li>
<script type="math/tex">\displaystyle \lim_{x\to0}\dfrac{1+\sqrt{1-4x}}{2x}</script>显然不收敛。</li>
<li>
<script type="math/tex">\displaystyle \lim_{x\to0}\dfrac{1-\sqrt{1-4x}}{2x}=1</script>。</li>
</ul>
<p>不难知道选负号。</p>
<p>然后提取系数<script type="math/tex">[x^n]\dfrac{1-\sqrt{1-4x}}{2x}</script>
</p>
<p>如果你阅读了前面的话应该知道 <script type="math/tex">\displaystyle \sqrt{1-4x}=\sum_{n=0}^{+\infty}\tbinom{\frac12}{n}(-4x)^n</script>
</p>
<p>提取系数就可以发现我们需要的了 <script type="math/tex">C[n]=-\frac{(-4)^{n+1}\tbinom{\frac12}{n+1}}{2}</script>
</p>
<p>可以拆广义二项式系数。最终得到：
<script type="math/tex; mode=display">C[n]=\frac{\tbinom{2n}{n}}{n+1}</script>
我们又双叒叕推出了一个（伪）通项。</p>
<h3 id="4">例题4：<a href="https://www.luogu.com.cn/problem/P5488">差分与前缀积</a></h3>
<p><del>这个我熟，我会 <script type="math/tex">\Theta(nk)</script></del></p>
<p>考虑一个数列 <script type="math/tex">\langle a_0,a_1,a_2,\rangle</script> ，对其 <script type="math/tex">\mathbf{OGF}</script> 做前缀和和差分的结果。</p>
<p>记当前的生成函数为<script type="math/tex">F(x)</script>
</p>
<p>对于前缀和，发现 <script type="math/tex">a_n^\prime=\sum_{i=1}^na_i\times 1</script> ，那么构造一个生成函数<script type="math/tex">G(x)=1+x+x^2+\ldots</script>，就有：</p>
<p>
<script type="math/tex; mode=display">F^\prime(x)=F(x)\times G(x)</script>
</p>
<p>(这里的 <script type="math/tex">F^\prime(x)</script> 指做完前缀和后的生成函数)</p>
<p>我们知道乘法具有结合律，因此做完 <script type="math/tex">k</script> 次后的生成函数就为 <script type="math/tex">F(x)\times G^k(x)</script>
</p>
<p>对于前缀积，发现 
<script type="math/tex; mode=display">F^\prime(x)=F(x)-xF(x)=F(x)\times(1-x)</script>
</p>
<p>可以理解为：<script type="math/tex">xF(x)</script> 可以理解为把整个数列右移。</p>
<p>于是也可以写成幂形式： <script type="math/tex">F(x)\times(1-x)^k</script>
</p>
<p>都看到这里了写个多项式快速幂应该难不倒你吧QwQ</p>
<h2 id="mathbfegf">指数生成函数 <script type="math/tex">\mathbf{EGF}</script>
</h2>
<p>我们令 <script type="math/tex">f_k(x)=\frac{x^k}{k!}</script> 就可以得到<strong>指数生成函数</strong>（<script type="math/tex">\mathbf{EGF}</script>，<script type="math/tex">\rm exponential\quad generating\quad function</script>）了。
<script type="math/tex; mode=display">F(x)=a_0+\frac{a_1x}{1!}+\frac{a_2x^2}{2!}+\frac{a_3x^3}{3!}+\ldots</script>
首先来看一个数列 <script type="math/tex">\{1,1,1,\ldots\}</script>，ta的 <script type="math/tex">\mathbf{EGF}</script> 就为
<script type="math/tex; mode=display">F(x)=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\ldots</script>
惊奇的发现：这不就是 <script type="math/tex">e^x</script> 的泰勒展开吗。这也是指数其名字的由来。来看几个比较简单的生成函数：
<script type="math/tex; mode=display">
\boxed{
\begin{aligned}
&\{1,1,1,1,\ldots\}\stackrel{\mathbf{EGF}}{\longrightarrow}e^x\\
&\{1,-1,1,-1,\ldots\}\stackrel{\mathbf{EGF}}{\longrightarrow} e^{-x}\\
&\{1,0,1,0,\ldots\}\stackrel{\mathbf{EGF}}{\longrightarrow} \frac{e^x+e^{-x}}{2}\\
&\{0,1,0,1,\ldots\}\stackrel{\mathbf{EGF}}{\longrightarrow}  \frac{e^x-e^{-x}}{2}\\
&\{1,c,c^2,c^3,\ldots\}\stackrel{\mathbf{EGF}}{\longrightarrow} e^{cx}
\end{aligned}
}
</script>
都可以用泰勒展开得到。</p>
<p>那么指数生成函数有什么意义呢？</p>
<h3 id="1_2">例题1：数<strong>数</strong>问题</h3>
<p>用两个<script type="math/tex">1</script>，两个<script type="math/tex">3</script>，一个<script type="math/tex">5</script>，能排成多少个不同的四位数？
<script type="math/tex; mode=display">\mathbf{EGF}\{1,1,1\}\times\mathbf{EGF}\{1,1\}\times\mathbf{EGF}\{1,1\}</script>
提取 <script type="math/tex">\frac{x^4}{4!}</script> 的系数即为答案。</p>
<p>还是考虑多项式乘法，我们设<script type="math/tex">A(x)\times B(x)=C(x)</script>：<script type="math/tex">\frac{C_n}{n!}=\sum_{i=0}^n\frac{A_i}{i!}\frac{B_{n-i}}{(n-i)!}</script>，可以写成组合数的形式：
<script type="math/tex; mode=display">C_n=\sum_{i=0}^n\tbinom{n}{i}A_iB_{n-i}</script>
可以理解成对 <script type="math/tex">A</script> 、 <script type="math/tex">B</script> 内部的方案放到大小为 <script type="math/tex">n</script> 的序列中，对其中 <script type="math/tex">i</script> 个位置选用 <script type="math/tex">A</script> 内部的方案，剩下的位置选用 <script type="math/tex">B</script> 的方案。在回顾例题就迎刃而解了。</p>
<h3 id="2_1">例题2：染色问题</h3>
<p>用红蓝绿三种颜色，涂一个长度为 <script type="math/tex">n</script> 的纸条，使得红色和蓝色的个数是偶数，求方案数。</p>
<p>这显然符合我们刚刚的 <script type="math/tex">\mathbf{EGF}</script> ，分别考虑三种颜色的:
- 红色和蓝色是偶数 <script type="math/tex">\{1,0,1,0,\ldots\}\stackrel{\mathbf{EGF}}{\longrightarrow} \frac{e^x+e^{-x}}{2}</script>
</p>
<ul>
<li>绿色是任意数 <script type="math/tex">\{1,1,1,1,\ldots\}\stackrel{\mathbf{EGF}}{\longrightarrow}e^x</script>
</li>
</ul>
<p>把这三者乘起来就是答案的 <script type="math/tex">\mathbf{EGF}</script> 了</p>
<p>
<script type="math/tex; mode=display">(\frac{e^x+e^{-x}}{2})^2e^x=\frac{e^{3x}+2e^{x}+e^{-x}}{4}</script>
</p>
<p>提取系数(也可以理解为还原 <script type="math/tex">\mathbf{EGF}</script> )得到：<script type="math/tex">\frac{3^n+2+(-1)^n}{4}</script>
</p>
<h3 id="3-i">例题3：<a href="https://www.luogu.com.cn/problem/P5219">无聊的水题 I</a></h3>
<p><del>有一说一确实又无聊又水</del></p>
<p>一棵有编号无根树唯一对应一个<code>prufer</code>序列，并且，度数为其在序列中的出现次数加 <script type="math/tex">1</script> 。我们希望能求出满足的序列数使其出现的最大次数为 <script type="math/tex">M-1</script>。</p>
<p>最大次数恰好为 <script type="math/tex">M-1</script> 不太好做，考虑差分：</p>
<ul>
<li>
<script type="math/tex">\text{至多M-1次}-\text{至多M-2次}=\text{恰好M-1次}</script>
</li>
</ul>
<p>于是剩下的就是套路了。</p>
<p>于是对每一个节点写出在序列中的 <script type="math/tex">\mathbf{EGF}</script>:
<script type="math/tex; mode=display">F(x)=\sum_{i=0}^m\frac{x^i}{i!}</script>
每个节点的生成函数都是一样的，答案的生成函数就是<script type="math/tex">F^N(x)</script>。</p>
<p>对于<script type="math/tex">m=M-1,M-2</script>分别求值做差即可。</p>
<h2 id="mathbfpgf">概率生成函数 <script type="math/tex">\mathbf{PGF}</script>
</h2>
<p>概率生成函数与上面两种略有不同，先来看一下<strong>概率生成函数</strong>(<script type="math/tex">\mathbf{PGF}</script>,<script type="math/tex">\rm probabilistic\quad generating\quad function</script>)</p>
<p>设 <script type="math/tex">P(A)</script> 为 <script type="math/tex">A</script> 为真的概率。</p>
<p>对于一个离散随机变量 <script type="math/tex">X</script>:
<script type="math/tex; mode=display">F(x)=\sum P(X=i)x^i</script>
这个不太好看的柿子有很多神奇的结论：</p>
<ol>
<li>
<p>根据定义显然有 <script type="math/tex">\sum P(X=i)=1</script>，即<script type="math/tex">F(1)=1</script>
</p>
</li>
<li>
<p>
<script type="math/tex">E(X)=\sum_{i}P(X=i)i=F^\prime(1)</script>
</p>
</li>
<li>
<p>方差也咕咕咕了</p>
</li>
</ol>
<p>其实等于号可以改成大于号，不过上面的性质就不满足了。</p>
<p>很多时候概率生成函数只是一个工具，实际使用中最后的结果往往与其无关。</p>
<p>直接看例题吧。</p>
<h3 id="1ctsc2006">例题1：<a href="https://www.luogu.com.cn/problem/P4548">[CTSC2006]歌唱王国</a></h3>
<p>设 <script type="math/tex">F_i</script> 为恰好到第 <script type="math/tex">i</script> 次结束的概率，<script type="math/tex">G_i</script> 表示到第 <script type="math/tex">i</script> 次还未结束的概率。<script type="math/tex">F(x)</script> 、 <script type="math/tex">G(x)</script> 分别为两者的 <script type="math/tex">\mathbf{PGF}</script>
</p>
<p>那么唱一个数，要么结束要么没结束，因此有：
<script type="math/tex; mode=display">F(x)+G(x)=xG(x)+1</script>
对比系数，左边 <script type="math/tex">[x^n]</script> 表示 <script type="math/tex">n</script> 次恰好结束与 <script type="math/tex">n</script> 次还未结束的概率，右侧 <script type="math/tex">[x^n]xG(x)=G[n-1]</script> ,就是 <script type="math/tex">n-1</script>次未结束的概率。因为一定会结束，所以两者相等。</p>
<p>两边同时求导：
<script type="math/tex; mode=display">
\begin{aligned}
F^\prime(x)+G^\prime(x)&=xG^\prime(x)+G(x)\\
F^\prime(1)&=G(1)
\end{aligned}
</script>
</p>
<p>利用到字符串本身的一些性质。对于序列 <script type="math/tex">A</script>，如果 <script type="math/tex">A[1:i]=A[len-i+1:len]</script> ，即又是前缀又是后缀，那么称其为一个 <script type="math/tex">\rm border</script>。</p>
<p>能够写出一个奇怪的等式：
<script type="math/tex; mode=display">G(x)\times(\frac1mx)^L=\sum_{A[1:i] \rm is\ border}F(x)\times(\frac1mx)^{L-i}</script>
左边是强制令其结束，右边是因为强制结束时可能已经结束，此时必定最后是一个 <script type="math/tex">\rm border</script> (可以画个图理解一下)</p>
<p><img alt="高清大图" src="https://cdn.luogu.com.cn/upload/image_hosting/cpzpot8t.png"></p>
<p>那么把 <script type="math/tex">x=1</script> 就可以出答案了
<script type="math/tex; mode=display">F^\prime(1)=G(1)=\sum_{A[1:i]\rm is\ border}F(1)m^i=\sum_{A[1:i]\rm is\ border}m^i</script>
然后<code>hash</code>  <code>kmp</code>就十分简单了。</p>
<h3 id="2-sdoi2017">例题2： <a href="https://www.luogu.com.cn/problem/P3706">[SDOI2017]硬币游戏</a></h3>
<p>把上一题扩展一下，就可以做这道题了。</p>
<p>我们用 <script type="math/tex">F_k[i]</script> 表示第 <script type="math/tex">k</script> 个人走 <script type="math/tex">i</script> 步结束(即胜利)的概率， <script type="math/tex">G[i]</script> 表示走 <script type="math/tex">i</script> 步还未结束的概率， <script type="math/tex">F_k(x)</script> 与 <script type="math/tex">G(x)</script> 为它们的 <script type="math/tex">\mathbf{PGF}</script> ，不难发现下面两个等式：
<script type="math/tex; mode=display">\begin{aligned}
&\sum_{i}F_i(1)=1\\
&G(x)+\sum_{i}F_i(x)=xG(x)+1
\end{aligned}</script>
第一个等式是因为必然会结束，第二个是例题1的等式扩展到多个串的情况。我们要求的即为 <script type="math/tex">F_i(1)</script> 。考虑在 <script type="math/tex">G[i]</script> 后面加一个串强制令其结束，设加的是第 <script type="math/tex">i</script> 个串。
<script type="math/tex; mode=display">G(x)\times(\frac12x)^L=\sum_{j}\sum_{A_i[1:k]=A_j[L-k+1,L]}F_j(x)\times(\frac12x)^{L-k}</script>
令 <script type="math/tex">x=1</script> 得到：
<script type="math/tex; mode=display">G(1)=\sum_{j}\sum_{A_i[1:k]=A_j[L-k+1,L]}F_j(1)\times 2^k</script>
在结合第一个等式，我们就可以列出 <script type="math/tex">n+1</script> 个方程，恰好有 <script type="math/tex">n+1</script> 个未知数。高斯消元即可。</p>
<h1 id="_18">生成函数&amp;卷积进阶</h1>
<p>一些讨论整理在这里。</p>
<h2 id="exp">
<script type="math/tex">\exp</script> 的组合意义</h2>
<p>众所周知 <script type="math/tex">\exp x</script> 是 <script type="math/tex">\sum\limits_{i=0}^\infty\dfrac{x^i}{i!}</script> ，那么 <script type="math/tex">\exp F(x)</script> 会得到什么呢？
先暴力展开在说：
<script type="math/tex; mode=display">\exp F(x)=\sum_{i=0}^\infty\frac{F^i(x)}{i!}</script>
这个东西是有组合意义的。假如 <script type="math/tex">F(x)</script> 是“单个元素”的 <script type="math/tex">\mathbf{EGF}</script> ,那么 <script type="math/tex">\exp F(x)</script> 就是把这些元素拼接起来的 <script type="math/tex">\mathbf{EGF}</script>
</p>
<p>展开式就相当于枚举有几个元素，多次卷积拼接，由于元素之间无序需要除以个数的阶乘。</p>
<h3 id="12013">例题1：<a href="https://www.luogu.com.cn/problem/P4841">[集训队作业2013]城市规划</a></h3>
<p>如果我们用 <script type="math/tex">F[i]</script> 表示 <script type="math/tex">i</script> 个点组成的<strong>连通图</strong>个数，<script type="math/tex">G[i]</script> 表示 <script type="math/tex">i</script> 个点组成的 <strong>图</strong> 的个数，<script type="math/tex">F(x)</script> 与 <script type="math/tex">G(x)</script> 分别为它们的 <script type="math/tex">\mathbf{EGF}</script>
</p>
<p>可以认为是若干个 连通图 组成了一张图，因此可以有：<script type="math/tex">\exp F(x)=G(x)</script>
</p>
<p>于是 <script type="math/tex">F(x)=\ln G(x)</script> 。 <script type="math/tex">G(x)</script> 是很好求的，因为 <script type="math/tex">G[i]=2^{\tbinom{i}{2}}</script>
</p>
<h3 id="2_2">例题2：<a href="https://www.luogu.com.cn/problem/P5434">有标号荒漠计数</a></h3>
<ul>
<li>先来考虑仙人掌怎么做</li>
</ul>
<p>本来是无根的，我们强制令其有根。因为有标号，有根方案数除以节点数就是无根方案数。</p>
<p>用 <script type="math/tex">F(x)</script> 表示方案数的 <script type="math/tex">\mathbf{EGF}</script>
</p>
<p>那么我们先钦定一个点为根，那么这个点可以这样连边：</p>
<table>
<thead>
<tr>
<th>情况一</th>
<th>情况二</th>
<th>情况三</th>
<th>...</th>
</tr>
</thead>
<tbody>
<tr>
<td><img alt="" src="https://cdn.luogu.com.cn/upload/image_hosting/8sdlpvwe.png"></td>
<td><img alt="" src="https://cdn.luogu.com.cn/upload/image_hosting/jpdnrwru.png"></td>
<td><img alt="" src="https://cdn.luogu.com.cn/upload/image_hosting/n3rrkftq.png"></td>
<td>...</td>
</tr>
<tr>
<td>
<script type="math/tex">F(x)</script>
</td>
<td>
<script type="math/tex">\frac{F(x)^2}{2}</script>
</td>
<td>
<script type="math/tex">\frac{F(x)^3}{2}</script>
</td>
<td>...</td>
</tr>
</tbody>
</table>
<p>除以 <script type="math/tex">2</script> 是因为顺时针与逆时针是一种方案。这部分的生成函数就是 <script type="math/tex">\displaystyle F(x)+\frac12\sum_{i=2}F(x)^i</script>。</p>
<p>这只是根上的一个<strong>基本单位</strong>，可以由任意个组成，不难写出方程：
<script type="math/tex; mode=display">F(x)=x\exp(F(x)+\frac12\sum_{i=2}^\infty F(x)^i)</script>
</p>
<p>后面一串是一个等比数列求和。拆开来就变成 <script type="math/tex">\exp\frac{2F(x)-F(x)^2}{2-2F(x)}</script>
</p>
<p>熟不熟悉？</p>
<p>对 <script type="math/tex">F(x)</script> 的 <script type="math/tex">x^i</script> 除以 <script type="math/tex">i</script> 就得到无根有标号仙人掌的数目了。以下的 <script type="math/tex">F(x)</script> 指无根。</p>
<p>那么现在荒漠的 <script type="math/tex">\mathbf{EGF}</script> 就是 <script type="math/tex">\exp F(x)</script> 了</p>
<h2 id="_19">差/和卷积</h2>
<p>在实际卷题的过程中，我们的卷积形式可能不是很明显，比如下边这个柿子：<script type="math/tex">H[j]=\sum_{i=j}^nF[i]\times G[i-j]</script>
</p>
<p>但是这个东西也是可以求的，我们只需要翻转 <script type="math/tex">F</script> 得到 <script type="math/tex">F_R</script> ,在翻转 <script type="math/tex">H</script> 得到 <script type="math/tex">H_R</script>,就可以得到显然的卷积式: <script type="math/tex">H_R[n-j]=\sum_{i=j}^nF_R[n-i]\times G[i-j]</script> ,这个式子就可以直接卷了。</p>
<p>同样还有类似的<strong>和卷积</strong>，思路还是翻转形成卷积。
<script type="math/tex; mode=display">H[j]=\sum_{i=0}F[i]\times G[i+j]</script>
我们翻转 <script type="math/tex">F</script> 得到 <script type="math/tex">F_R</script> ,并把 <script type="math/tex">H</script> 整体 <script type="math/tex">n</script> 右移可以得到：
<script type="math/tex; mode=display">H[n+j]=\sum_{i=0}F_R[n-i]\times G[i+j]</script>
实战中常常会用到类似的套路。</p>
<h2 id="bluesteins-algorithm">Bluestein's algorithm</h2>
<p><code>Bluestein's algorithm</code> 算法可以在 <script type="math/tex">\Theta(n\log n)</script>的时间内完成任意长度的 <script type="math/tex">\mathbb{DFT}</script>
</p>
<p>具体来说是这样的：
<script type="math/tex; mode=display">
\begin{aligned}
y_k&=\sum_{i=0}^{n-1}a_i\omega_n^{ki}\\
&=\sum_{i=0}^{n-1}a_i\omega_{2n}^{-(k-i)^2 +k^2+i^2}\\
&=\omega_{2n}^{k^2}\sum_{i=0}^{n-1}a_i \omega_{2n}^{i^2}\times\omega_{2n}^{-(k-i)^2}
\end{aligned}
</script>
可以理解为拆指数形成卷积形式。但有些毒瘤题目中可能会不保证 <script type="math/tex">\omega_{2n}</script> 存在，因此下面介绍另一种常用方法：
<script type="math/tex; mode=display">
\begin{aligned}
y_k&=\sum_{i=0}^{n-1}a_i\omega_n^{ki}\\
&=\sum_{i=0}^{n-1}a_i\omega_n^{\binom{k+i}{2}-\binom{i}{2}-\binom{k}{2}}\\
&=\omega_{n}^{-\binom{k}{2}}\sum_{i=0}^{n-1}a_i\omega_n^{-\binom{i}{2}}\times\omega_n^{\binom{k+i}{2}}
\end{aligned}
</script>
这个形式显然可以卷积了。可以参见上文的 <strong>差/和卷积</strong>。</p>
<h2 id="_20">单位根反演</h2>
<p>有公式 
<script type="math/tex; mode=display">[n|k]=\frac1n\sum_{i=0}^{n-1}\omega_n^{ik}</script>
证明直接分类讨论即可：
- <script type="math/tex">n|k</script> ，<script type="math/tex">\omega_n^{ik}=1</script> ,上式显然等于 <script type="math/tex">1</script>
- <script type="math/tex">n\not | k</script>，等比数列求和得到：<script type="math/tex">\dfrac{1}{n}\times \dfrac{\omega_n^{nk}-\omega_n^0}{\omega_n^k-1}=0</script>
</p>
<p>可以直接记结论。</p>
<h3 id="1_3">例题1：<a href="[小猪佩奇学数学](https://www.luogu.com.cn/problem/P5591)">小猪佩奇学数学</a></h3>
<p>给定 <script type="math/tex">n,p,k</script> 询问 <script type="math/tex">\sum_{i=0}^n \binom n i \times p^{i} \times \left\lfloor \frac{i}{k} \right\rfloor \bmod 998244353</script>
</p>
<p>
<script type="math/tex">k\in\{2^{w}|0\leq w\leq20\}</script>就是在保证单位根的存在。</p>
<p>然后就爆推式子。</p>
<p>向下取整可以拆成容易算的 <script type="math/tex">\lfloor\frac{i}{k} \rfloor=\frac{i-i \bmod k}{k}</script>
</p>
<p>原式就可以写成 <script type="math/tex">\frac{1}{k}(\sum_{i=0}^n\tbinom{n}{i}p^ii-\sum_{i=0}^n\tbinom{n}{i}p^i(i\bmod k))</script>
</p>
<p>分开来看式子。</p>
<p>由于组合数的定义： <script type="math/tex">\tbinom{n}{i}i=\frac{n!}{i!(n-i)!}i=\frac{n(n-1)!}{(i-1)!(n-i)!}=\tbinom{n-1}{i-1}n</script>
<script type="math/tex; mode=display">
\begin{aligned}
&\sum_{i=0}^n\tbinom{n}{i}p^ii\\
&=\sum_{i=1}^n\tbinom{n-1}{i-1}np^i\\
&=np\sum_{i=0}^{n-1}\tbinom{n-1}{i}p^{i}\\
&=np(p+1)^{n-1}
\end{aligned}
</script>
<script type="math/tex; mode=display">
\begin{aligned}
&\sum_{i=0}^n\sum_{t=0}^{k-1}[i\bmod k=t]\tbinom{n}{i}p^it\\
&=\sum_{i=0}^n\sum_{t=0}^{k-1}[k|(i-t)]\tbinom{n}{i}p^it\\
&=\sum_{i=0}^n\sum_{t=0}^{k-1}\frac{1}{k}\sum_{j=0}^{k-1}\omega_k^{j(i-t)}\tbinom{n}{i}p^it\\
&=\frac{1}{k}\sum_{j=0}^{k-1}\sum_{t=0}^{k-1}t\omega_k^{-tj}\sum_{i=0}^n\tbinom{n}{i}(\omega_k^jp)^i\\
&=\frac{1}{k}\sum_{j=0}^{k-1}\sum_{t=0}^{k-1}t\omega_k^{-tj}(\omega_k^jp+1)^n
\end{aligned}
</script>
所以只需要对于<script type="math/tex">j\in[0,k)</script>求出后面一串的值就行了。可以使用<code>Bluestein's Algorithm</code>拆指数具体过程就不展开了。</p>
<p>最后能得到：
<script type="math/tex; mode=display">\frac{1}{k}\sum_{j=0}^{k-1}\omega_k^\tbinom{j}{2}(\omega_k^jp+1)^n\sum_{t=0}^{k-1}t\omega_k^{\tbinom{t}{2}}\times \omega_k^{-\tbinom{t+j}{2}}</script>
</p>
<p>这就可以卷积了。不过注意 <script type="math/tex">\omega_k^{-\tbinom{t+j}{2}}</script> 的数组要倍长。</p>
<h3 id="2hnoi2019">例题2：<a href="https://www.luogu.com.cn/problem/P5293">[HNOI2019]白兔之舞</a></h3>
<p>与上一题类似的操作，不过涉及一点点矩阵。</p>
<p>记<script type="math/tex">g_{i,j}</script>为走了<script type="math/tex">i</script>步到第二维为<script type="math/tex">j</script>的顶点（<strong>不钦定走那些列</strong>）的方案数，有：</p>
<p>
<script type="math/tex; mode=display">g_{i,j}=\sum_{k=1}^ng_{i-1,k}w_{k,j}</script>
</p>
<p>若记 <script type="math/tex">G_i=(g_{i,1},g_{i,2},\ldots,g_{i,n})</script>
</p>
<p>
<script type="math/tex; mode=display">
G_0=(\underbrace{0,\ldots,0}_{x-1},1,\underbrace{0,\ldots,0}_{n-x})
</script>
<script type="math/tex; mode=display">
S=
\begin{pmatrix}
w_{1,1}&\cdots&w_{1,n}\\
\vdots&\ddots&\vdots\\
w_{n,1}&\cdots&w_{n,n}
\end{pmatrix}
</script>
有：<script type="math/tex">G_i=G_{i-1}\times S</script>，即<script type="math/tex">G_i=G_0\times S^i</script>
</p>
<p>但此时我们没有考虑白兔兔每次走了几步。所以我们还需要考虑<script type="math/tex">i</script>步走了那些列。实际上就是在<script type="math/tex">L</script>个位置上选了<script type="math/tex">i</script>个位置 <del>唱</del> 跳，也就是<script type="math/tex">\tbinom{L}{i}g_{i,j}=\tbinom{L}i(G_0S^i)_{1,y}</script>
</p>
<p>那么此时我们已经表示出跳了<script type="math/tex">i</script>的方案数。来考虑答案，列出式子开始乱推：
<script type="math/tex; mode=display">
\begin{aligned}
ans_t&=\sum_{i=0}^L[i\bmod k=t]\tbinom{L}{i}g_{i,y}=\sum_{i=0}^L[k|(i-t)]\tbinom{L}{i}g_{i,y}\\
&=\sum_{i=0}^L\frac{1}{k}\tbinom{L}{i}g_{i,y}\sum_{j=0}^{k-1}\omega_{k}^{(i-t)j}=\frac{1}{k}\sum_{i=0}^L\tbinom{L}{i}g_{i,y}\sum_{j=0}^{k-1}\omega_{k}^{ij}\omega_{k}^{-tj}\\
&=\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=0}^L\tbinom{L}{i}g_{i,y}\omega_{k}^{ij}\\
&=\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{-tj}\sum_{i=0}^L\tbinom{L}{i}\omega_{k}^{ij}\times(G_0S^i)_{1,y}
\end{aligned}
</script>
矩阵那部分事实上也可以先提取公因式再求和再取下标，即：
<script type="math/tex; mode=display">
\begin{aligned}
&=\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{-tj}(G_0\sum_{i=0}^L\tbinom{L}{i}\omega_{k}^{ij}\times S^i)_{1,y}\\
&=\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{-tj}(G_0\sum_{i=0}^L\tbinom{L}{i}(\omega_{k}^{j}\times S)^i)_{1,y}\\
&=\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{-tj}(G_0\sum_{i=0}^L\tbinom{L}{i}(\omega_{k}^{j}\times S)^iI^{L-i})_{1,y}\\
&=\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{-tj}(G_0(\omega_k^jS+I)^L)_{1,y}
\end{aligned}
</script>
</p>
<p>如果我们记<script type="math/tex">f_i=(G_0(\omega_k^iS+I)^L)_{1,y}</script>，就可以吧答案写成比较简单的形式。
<script type="math/tex; mode=display">ans_t=\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{-tj}f_j</script>
</p>
<p>然后就是 <del>有手就行</del> 的<code>Bluestein's algorithm</code>了。
<script type="math/tex; mode=display">
\begin{aligned}
ans_t&=\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{-\tbinom{t+j}{2}+\tbinom{t}{2}+\tbinom{j}{2}}f_j\\
&=\frac{\omega_{k}^\tbinom{t}{2}}{k}\sum_{j=0}^{k-1}\omega_{k}^{-\tbinom{t+j}{2}}\times \omega_{k}^\tbinom{j}{2}f_j
\end{aligned}
</script>
卷积就不难了。</p>
<h2 id="_21">二项式反演</h2>
<p>有时做题中<strong>恰好</strong>等词不是怎么好做，我们使用二项式反演可以由<strong>至少</strong>得到他。（这个至少其实是假的，如果真正意义上的至少只需要差分就行了</p>
<p>
<script type="math/tex; mode=display">F[n]=\sum_{i=0}(-1)^i\binom{n}{i}G[i]\Longleftrightarrow G[n]=\sum_{i=0}(-1)^i\dbinom{n}{i}F[i]</script>
以及另两种常用的形式
<script type="math/tex; mode=display">F[n]=\sum_{i=0}\binom{n}{i}G[i] \Longleftrightarrow G[n]=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}F[i]</script>
<script type="math/tex; mode=display">F[n]=\sum_{i=n}\binom{i}{n}G[i] \Longleftrightarrow G[n]=\sum_{i=n}(-1)^{i-n}\binom{i}{n}F[i]</script>
</p>
<h3 id="1haoi2018">例题1：<a href="https://www.luogu.com.cn/problem/P4491">[HAOI2018]染色</a></h3>
<p>设 <script type="math/tex">G[k]</script> 表示有 <script type="math/tex">k</script> 种颜色<strong>恰好</strong>出现了 <script type="math/tex">S</script> 次</p>
<p>那么我们尝试先钦定 <script type="math/tex">k</script> 种颜色，并强行令其出现恰好 <script type="math/tex">S</script> 次，我们记做 <script type="math/tex">F[k]</script> ,不难有：
<script type="math/tex; mode=display">F[k]=\binom{m}{k}\frac{n!}{(S!)^k(n-kS)!}(m-k)^{n-kS}</script>
考虑这么算对于一个<strong>恰好</strong>为 <script type="math/tex">i</script> 个情况，会计算<script type="math/tex">\binom{i}{k}</script> 遍，因为同样是恰好 <script type="math/tex">i</script> 个，钦定的 <script type="math/tex">k</script> 个不同会重复计算。</p>
<p>于是：
<script type="math/tex; mode=display">F[n]=\sum_{i=n}\binom{i}{n}G[i] \Longleftrightarrow G[n]=\sum_{i=n}(-1)^{i-n}\binom{i}{n}F[i]</script>
这个东西也可以卷，拆开组合数就十分明显了QwQ。
<script type="math/tex; mode=display">
\begin{aligned}
G[n]&=\sum_{i=n}(-1)^{i-n}\frac{i!}{n!(i-n)!}F[i]\\
&=\frac{1}{n!}\sum_{i=n} i!F[i] \frac{(-1)^{i-n}}{(i-n)!}
\end{aligned}
</script>
可以参见 差/和卷积</p>
<h3 id="2cts2019">例题2：<a href="https://www.luogu.com.cn/problem/P5401">[CTS2019]珍珠</a></h3>
<p>记颜色<script type="math/tex">c</script>有<script type="math/tex">cnt_c</script>个，一种方案合法当且仅当：<script type="math/tex">\sum_{i=1}^Dcnt_i\bmod 2\le m</script>
</p>
<p>简单推导得到：<script type="math/tex">\sum_{i=1}^Dcnt_i\bmod 2\le n-2m</script>。注意两种情况需要特判。</p>
<p>记恰好有<script type="math/tex">k</script>个为奇数方案为<script type="math/tex">G[k]</script>，<strong>至少</strong>有<script type="math/tex">k</script>个为奇数的方案为<script type="math/tex">F[k]</script>。</p>
<p>
<script type="math/tex; mode=display">F[n]=\sum_{i=n}\binom{i}{n}G[i] \Longleftrightarrow G[n]=\frac{1}{n!}\sum_{i=n} i!F[i] \frac{(-1)^{i-n}}{(i-n)!}</script>
</p>
<p>
<script type="math/tex">\text{方案的生成函数=选k个生成函数}\times\text{强制奇数生成函数}\times{放任自流生成函数}</script>
<script type="math/tex; mode=display">\begin{aligned}
F[k]=&\tbinom{D}{k}n!\times [x^n] \left(\frac{e^x-e^{-x}}{2}^k\right)\left(e^x\right)^{D-k}\\
=&\tbinom{D}{k}\frac{n!}{2^k}[x^n]\sum_{j=0}^k
\tbinom{k}{j}(-1)^{k-j}e^{x(D-2(k-j))}
\end{aligned}</script>
</p>
<p>
<script type="math/tex">e^{ax}=1+\frac{ax}{1!}+\frac{a^2x^2}{2!}+\frac{a^3x^3}{3!}+\ldots</script>，即 <script type="math/tex">e^{ax}</script> 为 <script type="math/tex">\mathbb{EGF}<1,a,a^2,a^3,\dots></script> ， <script type="math/tex">[x^n]e^{ax}=\frac{a^n}{n!}</script>
</p>
<p>
<script type="math/tex; mode=display">\begin{aligned}
=&\tbinom{D}{k}\frac{1}{2^k}\sum_{j=0}^k
\tbinom{k}{j}(-1)^{k-j}(D-2(k-j))^n\\
=&\frac{D!}{(D-k)!2^k}\sum_{j=0}^k
\frac{(-1)^j(D-2j)^n}{j!}\times\frac{1}{(k-j)!}\\
\end{aligned}</script>
</p>
<h2 id="ln-exp">
<script type="math/tex">\ln</script> 、 <script type="math/tex">\exp</script> 优化无限背包</h2>
<p>在 <script type="math/tex">\mathbf{OGF}</script> 的例题中我们已经知道可以用其求背包的方案数，就是各部分的 <script type="math/tex">\mathbf{OGF}</script> 的积。在选无限个的情况下，我们可以通过 <script type="math/tex">\ln</script> 把求集变成求和，再用 <script type="math/tex">\exp</script> 还原。</p>
<p>通常有下面的形式：
<script type="math/tex; mode=display">\ln(\frac{1}{1-x^i})=\sum_{j=1}^\infty \frac{x^{ij}}{j}</script>
证明：
<script type="math/tex">\ln \frac{1}{1-x_i}=-\ln(1-x_i)</script>
</p>
<p>对右式求导得到：<script type="math/tex">(-\ln(1-x_i))^\prime=\frac{ix^{i-1}}{1-x^i}</script>
</p>
<p>我们知道：<script type="math/tex">\frac{1}{1-x^i}</script>就是<script type="math/tex">1+x_i+x^{2i}+\ldots</script>的封闭形式，即<script type="math/tex">\sum_{j=0}^{+\infty}x^{ij}</script>
</p>
<p>带回，有：<script type="math/tex">\frac{ix^{i-1}}{1-x^i}=\sum_{j=0}^{+\infty}ix^{i(j+1)-1}=\sum_{j=1}^{+\infty}ix^{ij-1}</script>
</p>
<p>那么 
<script type="math/tex; mode=display">\ln\frac{1}{1-x^i}=\int \sum_{j=1}^{+\infty}ix^{ij-1} dx=\sum_{j=1}^{+\infty}\frac{x_{ij}}{j}</script>
</p>
<h3 id="1_4">例题1:<a href="https://www.luogu.com.cn/problem/P4389">付公主的背包</a></h3>
<p>对于体积为 <script type="math/tex">V</script> 的物品，其生成函数为 <script type="math/tex">1+x^V+x^{2V}+\ldots=\frac{1}{1-x^V}</script> 。</p>
<p>于是答案的生成函数 <script type="math/tex">F(x)</script> 就是所有乘起来。
<script type="math/tex; mode=display">F(x)=\prod_i\frac{1}{1-x^{V_i}}</script>
两边同取 <script type="math/tex">\ln</script> 就能去掉乘积了。
<script type="math/tex; mode=display">\ln F(x)=\sum_i\ln\left(\frac{1}{1-x^{V_i}}\right)</script>
在用刚刚的式子。
<script type="math/tex; mode=display">\ln F(x)=\sum_i\sum_{j=1}^\infty \frac{x^{V_ij}}{j}</script>
我们只需要前 <script type="math/tex">n</script> 项。如果我们记 <script type="math/tex">V_i=k</script> 的次数为 <script type="math/tex">cnt_k</script> ，那么：
<script type="math/tex; mode=display">\ln F(x)=\sum_i\sum_{j=1}^\infty \frac{cnt_ix^{ij}}{j}</script>
这个可以用调和级数 <script type="math/tex">\Theta(n\ln n)</script> 填系数。</p>
<h3 id="2sdoi2017">例题2：<a href="https://www.luogu.com.cn/problem/P3784">[SDOI2017] 遗忘的集合</a></h3>
<p>首先考虑 <script type="math/tex">a_i\in\{0,1\}</script> 表示第 <script type="math/tex">i</script> 个数选还是不选，不难发现第 <script type="math/tex">i</script> 个数的 <script type="math/tex">\mathbf{OGF}</script> 就为 <script type="math/tex">1+a_i(x^i+x^{2i}+x^{3i}+\ldots)</script> ，封闭形式为 <script type="math/tex">(\frac{1}{1-x^i})^{a_i}</script>
</p>
<p>随便推导一下得到：
<script type="math/tex; mode=display">\ln F(x)=\sum_{i=1}a_i\sum_{j=1}\frac{x^{ij}}{j}</script>
做过莫反的都知道，可以设<script type="math/tex">T=ij</script>
<script type="math/tex; mode=display">\ln F(x)=
\sum_{T=1}(\sum_{i|T}a^i\times\frac iT)x^T</script>
<script type="math/tex; mode=display">T[x^T]\ln F(x)=\sum_{i|T}a_i\times i</script>
中间的狄利克雷卷积已经很明显了。设两个数论函数 <script type="math/tex">f(T)=T[x^T]\ln F(x)</script>，<script type="math/tex">g(T)=a_T\times T</script> ，那么： <script type="math/tex">f=g * I</script>
两边同乘 <script type="math/tex">\mu</script> 得到：
<script type="math/tex; mode=display">f*\mu=g*I*\mu=g*(I*\mu)=g*\varepsilon=g</script>
<script type="math/tex">\Theta(n\ln n)</script>求<script type="math/tex">f*\mu</script>即可</p>
<h1 id="_22">群</h1>
<h2 id="_23">定义</h2>
<p>定义集合 <script type="math/tex">G</script> 和二元运算 <script type="math/tex">\times</script> ，记为 <script type="math/tex">(G,\times)</script>，满足以下条件的称为群：
1. 封闭性：<script type="math/tex">\forall a,b\in G,a\times b\in G</script>
</p>
<ol>
<li>
<p>结合律：<script type="math/tex">\forall a,b,c\in G,(a\times b)\times c=a\times(b\times c)</script>
</p>
</li>
<li>
<p>单位元（幺元）：<script type="math/tex">\exists e\in G,\forall a\in G,a\times e=e\times a=a</script>
</p>
</li>
<li>
<p>逆元：<script type="math/tex">\forall a\in G,\exists a^\prime\in G,a\times a^\prime=a^\prime\times a=e</script>，不难证明逆元唯一</p>
</li>
</ol>
<h2 id="_24">子群</h2>
<p>若 <script type="math/tex">H</script> 为 <script type="math/tex">G</script> 的一个子集，且 <script type="math/tex">(H,\times)</script> 构成一个群，那么称 <script type="math/tex">H</script> 为 <script type="math/tex">G</script> 的一个子群，记作 <script type="math/tex">H\leq G</script>
</p>
<p>如果 <script type="math/tex">g\in G</script>
- <script type="math/tex">gH=g\times h,h\in H</script> ,那么称其为 <script type="math/tex">H</script> 在 <script type="math/tex">G</script> 内关于 <script type="math/tex">g</script> 的左陪集。</p>
<ul>
<li>
<script type="math/tex">Hg=h\times g,g\in H</script> ,那么称其为 <script type="math/tex">H</script> 在 <script type="math/tex">G</script> 内关于 <script type="math/tex">g</script> 的右陪集。</li>
</ul>
<p>陪集的性质（以右陪集为例）：
1. <script type="math/tex">\forall g\in G,|H|=|Hg|</script>
</p>
<p>证明：因为逆元唯一，如果 <script type="math/tex">h_1\not=h_2</script> ，而且 <script type="math/tex">h_1\times g=p=h_2\times g</script> ，那么 <script type="math/tex">h2=p\times g^\prime=h_1</script> ，矛盾，因此 <script type="math/tex">h_1\times g\not=h_2\times g</script>
</p>
<ol>
<li>
<script type="math/tex">\forall g\in G,g\in Hg</script>
</li>
</ol>
<p>证明：<script type="math/tex">H</script> 是群，<script type="math/tex">H</script> 内一定存在一个单位元 <script type="math/tex">e</script> 满足 <script type="math/tex">e\times g=g</script> ，因此 <script type="math/tex">e\times g\in Hg\Leftrightarrow g\in Hg</script>
</p>
<ol>
<li>
<script type="math/tex">Hg=H\Leftrightarrow g\in H</script>
</li>
</ol>
<p>证明：假设 <script type="math/tex">g\not\in H</script> ，<script type="math/tex">eg\not\in Hg</script>，矛盾</p>
<ol>
<li>
<script type="math/tex">Ha=Hb\Leftrightarrow a\times b^{-1}\in H</script>
</li>
</ol>
<p>证明：由性质 <script type="math/tex">3</script> 可得</p>
<ol>
<li>
<script type="math/tex">Ha\cap Hb\not=\varnothing\Leftrightarrow Ha=Hb</script>
</li>
</ol>
<p>证明：假设 <script type="math/tex">c\in Ha,c\in Hb</script>，<script type="math/tex">\exists h_1,h_2</script> 满足 <script type="math/tex">h_1\times a=c,h_2\times b=c,a\times b^{-1}=h_1\times h_2^{-1}\in H</script> ，用性质 <script type="math/tex">4</script> 可以得到。</p>
<ol>
<li>
<script type="math/tex">H</script> 的全体右陪集的并为 <script type="math/tex">G</script>
</li>
</ol>
<p>证明：因为 <script type="math/tex">H</script> 存在单位元 <script type="math/tex">e</script>，<script type="math/tex">g</script> 取遍 <script type="math/tex">G</script> 中的每个元素。
<strong>一些表述</strong>
如果 <script type="math/tex">H\le G</script> ：</p>
<p>
<script type="math/tex">H/G</script> 表示 <script type="math/tex">H</script> 的所有左陪集 <script type="math/tex">\{gH|g\in G\}</script>
</p>
<p>
<script type="math/tex">[G:H]</script> 表示 <script type="math/tex">G</script> 中 <script type="math/tex">H</script> 的不同陪集的数量。</p>
<h2 id="_25">拉格朗日定理</h2>
<p><strong>拉格朗日定理</strong>：对于有限群 <script type="math/tex">G</script> 与有限群 <script type="math/tex">H</script>，若 <script type="math/tex">H</script> 为 <script type="math/tex">G</script> 的子群，那么有： <script type="math/tex">|H|\text{整除}|G|</script>
</p>
<p>即 <script type="math/tex">H</script> 的阶整除 <script type="math/tex">G</script> 的阶。</p>
<p>更具体点：<script type="math/tex">|H|\times [G:H]=|G|</script>
</p>
<p>证明：陪集大小和为 <script type="math/tex">|G|</script> ，陪集大小为 <script type="math/tex">|H|</script>，那么 <script type="math/tex">[G:H]=\frac{|G|}{|H|}</script>
</p>
<h2 id="_26">置换群</h2>
<p>设 <script type="math/tex">N=\{1,2,\ldots,n\}</script>，令 <script type="math/tex">M</script> 为 <script type="math/tex">N</script> 的一个排列（一个置换），然后定义两个置换 <script type="math/tex">A</script> 与 <script type="math/tex">B</script> 的 <script type="math/tex">\times</script> 操作得到一个新的置换 <script type="math/tex">C</script> 满足 <script type="math/tex">C_i=B_{A_i}</script>，让集合群 <script type="math/tex">G=(M,\times)</script>。</p>
<p><strong>循环</strong>：置换<br>
<script type="math/tex; mode=display">\begin{pmatrix}a_1&a_2&\ldots&a_{n-1}&a_n\\ a_2&a_3&\ldots&a_n&a_1\end{pmatrix}</script>
 称为 <script type="math/tex">n</script> 阶循环，记为 <script type="math/tex">(a_1\ a_2\ \ldots\ a_{n-1}\ a_n)</script>。不难发现任何一个置换都可以写作几个循环的乘积，并且结果唯一。</p>
<p><strong>「群作用」</strong>：对于一个集合 <script type="math/tex">M</script> 和群 <script type="math/tex">G</script>，若给定了一个二元函数 <script type="math/tex">\varphi(v,k)</script> 其中 <script type="math/tex">v</script> 为群中的元素，<script type="math/tex">k</script> 为集合元素，且有 <script type="math/tex">\varphi(e,k)=k</script>，<script type="math/tex">\varphi(g,\varphi(s,k))=\varphi(g\times s,k)</script> ，则称群 <script type="math/tex">G</script> 作用与 <script type="math/tex">M</script>
</p>
<h2 id="-">轨道-稳定子定理</h2>
<p><strong>轨道</strong>：作用在 <script type="math/tex">X</script> 上的置换群 <script type="math/tex">G</script>。<script type="math/tex">X</script> 中的元素 <script type="math/tex">x</script> 的 轨道 是在群 <script type="math/tex">G</script> 的作用下能够转移到的元素集合。<script type="math/tex">x</script> 的轨道被记为 <script type="math/tex">G(x)</script>，<script type="math/tex">g(x)</script> 表示群 <script type="math/tex">G</script> 元素 <script type="math/tex">g</script> 作用于 <script type="math/tex">x</script> 的群作用的返回值，即 <script type="math/tex">g(x)=\varphi(g,x)</script>。</p>
<p><strong>稳定子</strong>：<script type="math/tex">G^x=\{g|g(x)=x,g\in G\}</script>
</p>
<p><strong>轨道-稳定子定理</strong>：<script type="math/tex">|G^x||G(x)|=|G|</script>
</p>
<p>证明：由拉格朗日定理可以得出 <script type="math/tex">|G^x|[G:G^x]=|G|</script>，因此只需要证明 <script type="math/tex">[G:G^x]=|G(x)|</script>
</p>
<p>如果 <script type="math/tex">f(x)=g(x)</script>，那么 <script type="math/tex">f(x)g(x)^{-1}=e(x)\in G^x</script>。由于陪集的性质 <script type="math/tex">fG^x=gG^x</script>。因此 <script type="math/tex">fGx=gG^x\Leftrightarrow f=g</script>。</p>
<p>于是让 <script type="math/tex">gG^x</script> 对应 <script type="math/tex">g</script> 就可以不重不漏地表示所有陪集。</p>
<h2 id="rm-burnside">
<script type="math/tex">\rm Burnside</script> 引理</h2>
<p><strong>公式</strong>：定义 <script type="math/tex">G</script> 为一个作用于 <script type="math/tex">X</script> 置换群，如果 <script type="math/tex">x,y\in X</script> 在 <script type="math/tex">G</script> 的作用下可以相等即存在 <script type="math/tex">f\in G</script> 使得 <script type="math/tex">f(x)=y</script> 则定义 <script type="math/tex">x,y</script> 属于一个等价类，则不同的等价类数量为：</p>
<p>
<script type="math/tex; mode=display">|X/G|=\frac1{|G|}\sum_{g\in G}X^g</script>
</p>
<p>其中 <script type="math/tex">X^g</script> 为 <script type="math/tex">X</script> 在 <script type="math/tex">g</script> 的作用下的不动点数量，即满足 <script type="math/tex">g(x)=x</script> 的 <script type="math/tex">x</script> 的数量。</p>
<p>由于每个元素属于仅属于一个轨道，轨道内部在群 <script type="math/tex">G</script> 作用下互达，所以我们可以得到：</p>
<p>
<script type="math/tex; mode=display">|X/G|=\sum_{x\in X}\frac1{[G:G^x]}</script>
</p>
<p>根据轨道-稳定子定理，得到：</p>
<p>
<script type="math/tex; mode=display">[G:G^x]=\frac G{|G^x|}</script>
</p>
<p>
<script type="math/tex; mode=display">|X/G|=\sum_{x/in X}\frac{G^x}{G}</script>
</p>
<p>
<script type="math/tex; mode=display">|X/G|=\frac1{|G|}\sum_{x\in X}G^x</script>
</p>
<p>反过来，就是对于每一个群作用 <script type="math/tex">g</script> ，其作用下不动点的数量。</p>
<h2 id="rm-polya">
<script type="math/tex">\rm Pólya</script> 定理</h2>
<p>对于一个置换 <script type="math/tex">(a_1,a_2,\ldots,a_n)</script>。</p>
<p>在使用 <script type="math/tex">\rm Burnside</script> 解决染色问题的时候，我们需要求的是不动点的数量，而对于上述的置换，假设我们令每个 <script type="math/tex">i</script> 向 <script type="math/tex">a_i</script> 连一条边容易发现会得到若干个环，仔细思考，每个环的颜色应当相同。</p>
<p>我们定义这个环的数量为 <script type="math/tex">c(g)</script> 即置换 <script type="math/tex">g</script> 的轮换(环)数。</p>
<p>那么我们现在可以改写 <script type="math/tex">\rm Burnside</script> 定理为：</p>
<p>
<script type="math/tex; mode=display">\frac1{|G|}\sum_{g\in G}m^{c(g)}</script>
</p>
<h2 id="_27">一些例题</h2>
<h3 id="1p4980-polya">例题1：<a href="https://www.luogu.com.cn/problem/P4980">P4980 【模板】Pólya 定理</a></h3>
<p>考虑置换群 <script type="math/tex">G</script>，有顺时针旋转 <script type="math/tex">0,1,\ldots,n-1</script>。旋转 <script type="math/tex">i</script> 格轮换为 <script type="math/tex">\gcd(i,n)</script>，先给一个比较丑的证明：</p>
<p>假设一个点在 <script type="math/tex">p</script>，旋转 <script type="math/tex">k</script> 次，每次 <script type="math/tex">x</script> 格后回到原点，有：
<script type="math/tex; mode=display">
\begin{aligned}
&p+kx\equiv p\pmod n\Rightarrow kx\equiv 0\pmod n\\
&x|kx\quad \&\quad n|kx\Rightarrow kx=\operatorname{lcm}(x,n)=\frac{nx}{\gcd(n,x)}\\
&\large k=\frac{n}{\gcd(n,x)}
\end{aligned}
</script>
一共有 <script type="math/tex">n</script> 个数，每 <script type="math/tex">\frac n{\gcd(n,x)}</script> 个数构成一个环，共 <script type="math/tex">\gcd(n,x)</script> 个环。</p>
<p>于是直接上 <script type="math/tex">\rm Pólya</script> 定理
<script type="math/tex; mode=display">
\begin{aligned}
&\frac1n\sum_{i=1}^nn^{\gcd(i,n)}\\
&=\frac1n\sum_{d=1}^nn^d\sum_{i=1}^n[gcd(i,n)==d]\\
&=\frac1n\sum_{d|n}n^d\sum_{i=1}^{\frac nd}[\gcd(i,\frac nd)==1]\\
&=\frac1n\sum_{d|n}n^d\varphi(\frac nd)
\end{aligned}
</script>
</p>
<h3 id="2p2561-ahoi2002">例题2：<a href="https://www.luogu.com.cn/problem/P2561">P2561 [AHOI2002]黑白瓷砖</a></h3>
<p>设点的总数为 <script type="math/tex">N=\frac{n\times(n+1)}{2}</script>
</p>
<p>考虑置换群 <script type="math/tex">G</script>:
1. 不动，显然轮换数为 <script type="math/tex">N</script>
</p>
<ol>
<li>
<p>旋转 <script type="math/tex">120\degree,240\degree</script>，轮换数为 <script type="math/tex">\lceil\frac N3\rceil</script>
</p>
</li>
<li>
<p>沿三条对称轴翻转，对称轴上有 <script type="math/tex">\lceil\frac n2\rceil</script> 个点，轮换数为 <script type="math/tex">\frac{N-\lceil\frac n2\rceil}{2}+\lceil\frac n2\rceil</script>
</p>
</li>
</ol>
<p>于是得出答案：</p>
<p>
<script type="math/tex; mode=display">\frac16(2^N+2\times2^{\lceil\frac N3\rceil}+3\times2^{(\frac{N-\lceil\frac n 2\rceil} 2+\lceil\frac n2\rceil)})</script>
</p>
<h3 id="3sp419-transp-transposing-is-fun">例题3：<a href="https://www.luogu.com.cn/problem/SP419">SP419 TRANSP - Transposing is Fun</a></h3>
<p>如果一个数为 <script type="math/tex">\overbrace{X}^a\overbrace{Y}^b</script>，那么他将和 <script type="math/tex">\overbrace{Y}^b\overbrace{X}^a</script> 交换位置。朴素地交换是 <script type="math/tex">2^{a+b}</script> 的，是什么让它少了？举个简单的例子：<script type="math/tex">a=2,b=1</script>
<script type="math/tex; mode=display">\begin{pmatrix}
0&1\\
2&3\\
4&5\\
6&7
\end{pmatrix}\Rightarrow 
\begin{pmatrix}
0&4\\
1&5\\
2&6\\
3&7
\end{pmatrix}</script>
写出置换：
<script type="math/tex; mode=display">\begin{pmatrix}
0&1&2&3&5&6&7\\
0&2&1&5&6&5&7
\end{pmatrix}=(0)(12)(356)(7)</script>
每个循环内交换。设循环大小为 <script type="math/tex">x</script>，那么只需交换 <script type="math/tex">x-1</script> 次。若最终由 <script type="math/tex">K</script> 个循环，就少交换 <script type="math/tex">K</script> 次，答案为 <script type="math/tex">2^{a+b}-K</script>
</p>
<p>只需求出多少个循环即可。一个循环内的数有什么特点。由一开始的定义，他们都可以通过多次循环左移 <script type="math/tex">a</script> 位得到。（叫循环左移是因为要把高 <script type="math/tex">a</script> 位移到最低位）。</p>
<p>于是转化问题：一个 <script type="math/tex">a+b</script> 个珠子的环，可以染两种颜色。两个环通过若干次顺时针旋转 <script type="math/tex">a</script> 格得到的称为等价类。问有多少个等价类。等价类的数量就等于上面说的循环个数。</p>
<p>不过这个转 <script type="math/tex">a</script> 格与我们上面的问题略有不同。显然会有 <script type="math/tex">\gcd(a,a+b)=\gcd(a,b)</script> 个循环节，每个循环节互不影响。于是再转化：有 <script type="math/tex">\frac{a+b}{\gcd(a,b)}</script> 个大珠子，每个大珠子有 <script type="math/tex">2^{\gcd(a,b)}</script> 种染色方案。两个环若干次旋转一格能够相等称为同构，求数量。</p>
<p><img alt="抽象图1" src="https://cdn.luogu.com.cn/upload/image_hosting/8lsg4bk5.png">
<img alt="抽象图2" src="https://cdn.luogu.com.cn/upload/image_hosting/ekkyvjgm.png"></p>
<p>直接上 <script type="math/tex">\rm Pólya</script> 即可，推导与上面类似，设 <script type="math/tex">n=\frac{a+b}{\gcd(a,b)}</script>直接给出最终答案：
<script type="math/tex; mode=display">2^{a+b}-\frac{1}{n}\sum_{d|n}2^{gcd(a,b)\times d}\times\varphi(\frac nd)</script>
</p>
<p><a href="https://www.luogu.com.cn/problem/SP422">SP422 TRANSP2 - Transposing is Even More Fun</a> 用类似的方法也能过。</p>
<h3 id="4p4128-shoi2006">例题4：<a href="https://www.luogu.com.cn/problem/P4128">P4128 [SHOI2006] 有色图</a></h3>
<p><del>说好的有色图呢</del></p>
<p>设颜色数量为 <script type="math/tex">k</script>
</p>
<p>我们前面都是点置换，现在变成了边置换。</p>
<p>点置换的数量是 <script type="math/tex">n!</script> 显然不可以直接枚举。考虑一个数列 <script type="math/tex">a_1,a_2,\ldots,a_m</script> 满足 <script type="math/tex">\sum\limits_{i}a_i=n</script> 且 <script type="math/tex">a_i≥a_{i-1}</script>，其中 <script type="math/tex">a_i</script> 表示第 <script type="math/tex">i</script> 个循环节的大小，那么一个数列 <script type="math/tex">a_i</script> 与对应着若干点置换。</p>
<p>更具体的，若 <script type="math/tex">cnt_x</script> 表示 <script type="math/tex">a_i=x</script> 的数量，这个数列对应 <script type="math/tex">\displaystyle\frac{n!}{\prod_ia_i\prod cnt_x}</script> 个点置换。他们边置换的轮换数都是一样的。</p>
<ul>
<li>这条边在循环内部</li>
</ul>
<p>那么每个循环贡献的不动点数量为 <script type="math/tex">\lfloor \dfrac {a_i} 2 \rfloor</script>
</p>
<ul>
<li>这条边在两个循环之间</li>
</ul>
<p>两个循环贡献的不动点数量为 <script type="math/tex">\gcd(a_i,a_j)</script>
</p>
<p>最后对答案的贡献为：</p>
<p>
<script type="math/tex; mode=display">\frac{1}{|G|}\times\dfrac{n!}{\prod a_i \prod \dfrac{x}{cnt_x}}k^{\sum_{i=1}^m\lfloor \frac {a_i} 2 \rfloor+\sum_{1\le i<j\le m} \gcd(a_i,a_j)}</script>
</p>
<p>我们知道 <script type="math/tex">|G|=n!</script>，于是还可以消掉一些东西。</p>
<p>数列 <script type="math/tex">a</script> 的数量不会很大，具体可以参见 <a href="https://oeis.org/A296010">OEIS</a></p>
<p><a href="https://www.luogu.com.cn/problem/P4727">P4727 [HNOI2009]图的同构计数</a> 就是 <script type="math/tex">k=2</script> 的情况</p>
			</div>
			<div class="panel panel-default card" style="padding: 10px;height: 50px;font-size: 20px;">
				<a style="float: left;" href="\article\mould.html"><i class="fa fa-angle-double-left"></i></a><a style="float: right;" href="\article\poly.html"><i class="fa fa-angle-double-right"></i></a>
			</div>
			<div class="panel panel-default card" style="padding: 10px;font-size: 20px;" id="vcomments">
				
			</div>
			<script>
				new Valine({
					el: '#vcomments',
					appId: 'PAlFUPg0pQVTFTEo8gCB4BCf-gzGzoHsz',
					appKey: 'U38ejnLUiizJ6vLyp6ql4hRq',
					path: window.location.pathname
				})
			</script>
		</div>
		<div class="col-md-3">
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-info"></i>&emsp;
						<strong>文章信息</strong>
					</h3>
				</div>
                <div style="margin: 10px;">
                    <div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">标题</span>
    <span><font style="font-weight: bold">数数：从入门到放弃</font></span>
	</div><div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">日期</span>
    <span>2021-01-17 12:44:19</span>
	</div>
                </div>
				</div>
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-tag"></i>&emsp;
						<strong>标签</strong>
					</h3>
				</div>
				<div style="margin: 10px;">
					<a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/笔记/" class="tag"><span  style="background-color: rgb(82, 196, 26);">笔记</span></a>
				</div>
				</div>
				
			<div class="panel panel-default card">
					<div class="panel-heading">
						<h3 class="panel-title">
							<i class="fa fa-user-circle-o"></i>&emsp;
							<strong>caijicjl</strong>
						</h3>
					</div>
					<div style="width: 60%;display: inline-block;padding-top: 10px;">
						<ul class="propertyLinks" style="list-style-type: none;">
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/rating-16x16.png">
								Rating:&nbsp;
								<span style="font-weight:bold;color: gray ">312</span>
							</li>
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/star_blue_16.png">
								Contribution:&nbsp;
								<span style="color:gray;font-weight:bold;">0</span>
							</li>
						</ul>
						<ul class="nav-links">
							<li><a href="/settings/">Settings</a></li>
							<li><a href="/archives/">Blog</a></li>
							<li><a href="/teams">Teams</a></li>
							<li><a href="/submissions/dingdingsb">Submissions</a></li>
							<li><a href="/usertalk">Talks</a></li>
							<li><a href="/contests/with/dingdingsb">Contests</a></li>
						</ul>
					</div>
					<div style="display:inline-block;vertical-align: top;margin: 10px;text-align: center;">
						<div style="height:50px;width:50px"><img src="/img/avatar.png"/></div>
						<div><a href="https://www.luogu.com.cn/user/174304" style="font-weight:bold;color:gray">caijicjl</a></div>
					</div>
				</div>
		<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-external-link"></i>&emsp;
						<strong>画中画</strong>
					</h3>
				</div>
				<div style="width:100%;margin:10px">
				<input type="text" id="url"/>
				<input value="创建" type="button" onclick="creat('kk')" /> 
				</div>
		</div>
		<script src="/js/hitokoto.js"></script>
							

				
				<span id="kk"></span>
				<div  id="myScrollspy" class="card" style="width: 100%;"  data-spy="affix">
					<script src="/js/make_toc.js"></script>
				</div>
		</div>
	</div>
 </div>
</body>
</html>
